The present invention relates to techniques for processing an image in segments.
Data defining an image sometimes exceeds the capacity of a processor. Some prior art techniques divide an image into segments or tiles, each of which is small enough to be handled by the processor. Some operations cannot be performed at edges of segments, however, because they require data from adjacent segments. Therefore, some prior art techniques divide an image into overlapping segments, with the overlapping area at each edge being large enough that all operations can be validly performed in part of each segment. The results from the segment parts in which the operations are validly performed can then be combined to produce valid results for the entire image. Such techniques are inefficient, because the operations are also performed on the overlapping areas, obtaining invalid results.
Wilson, EP-A 293 701 (Wilson '701), describes parallel neighborhood processing techniques for matrices of numbers such as images. As shown and described in relation to FIG. 1, a parallel processing system includes an array of processing units each with a neighborhood processing element, data input and output means which are shift registers, and memory. Each neighborhood processing element can receive data from the processing elements on its immediate left and right. Left and right redundant co-memories support the memories of the left and right processing units, and provide appropriate neighborhood data to the right and left neighborhood processing elements, respectively. A duplicate copy of a data word transmitted to the left or right memory is also transmitted to and stored in the left or right co-memory, respectively.
Wilson '701 describes, in relation to FIGS. 2 and 3, how an image structure of W columns and H rows can be mapped into the memories. The data matrix is broken down into subsections, each with n columns and H rows, where n is equal to the number of processing units. The subsections, called ribbons, can be stored in the memories. At col. 9 line 55-col. 10 line 14, Wilson '701 indicates how the left processing element corresponds to the left edge of a ribbon and is connected to the right co-memory, which can be addressed to obtain the right edge of an adjacent ribbon. The right processing element, the right edge of a ribbon, is similarly connected to the left co-memory, which can be addressed to obtain the left edge of an adjacent ribbon.
Wilson '701 describes read cycles in relation to FIGS. 5A-5D, and write cycles in relation to FIGS. 6A-6D. In a read cycle, the co-memory addresses are displaced from the memory addresses, as shown by the cross-hatched areas.